export class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val === undefined ? 0 : val;
        this.left = left === undefined ? null : left;
        this.right = right === undefined ? null : right;
    }
}
function sortedArrayToBST(nums: number[]): TreeNode | null {
    // 如果数组为空，返回null
    if (nums.length === 0) return null;

    // 递归构建BST
    return buildBST(nums, 0, nums.length - 1);
}

function buildBST(nums: number[], left: number, right: number): TreeNode | null {
    // 基准情况：左边界大于右边界
    if (left > right) return null;

    // 选择中间位置作为根节点（对于偶数长度，选择中间偏右的位置）
    const mid = Math.floor((left + right) / 2);

    // 创建根节点
    const root = new TreeNode(nums[mid]);

    // 递归构建左子树和右子树
    root.left = buildBST(nums, left, mid - 1);
    root.right = buildBST(nums, mid + 1, right);

    return root;
}